πŸ‘©β€πŸ’» 60058. κ΄„ν˜Έ λ³€ν™˜

@Seongukbaek Posted June 11, 2022 Β· Updated June 11, 2022 Β· 3 min read

문제

Programmers - κ΄„ν˜Έ λ³€ν™˜

πŸ“ Logic

private String recursive(String p) { // 빈 λ¬Έμžμ—΄μΈ 경우 λ°˜ν™˜ if (Objects.equals(p, "")) return p; // u와 v둜 뢄리 String[] uv = splitString(p); String u = uv[0]; String v = uv[1]; // uκ°€ μ˜¬λ°”λ₯΄λ‹€λ©΄, v에 λŒ€ν•΄ recurvie()ν•œ κ²°κ³Όλ₯Ό λΆ™μ—¬ λ°˜ν™˜ if (isProper(u)) return u + recursive(v); // uκ°€ μ˜¬λ°”λ₯΄μ§€ μ•Šμ€ 경우 StringBuilder sb = new StringBuilder("("); sb.append(recursive(v)).append(")").append(reverseBracket(u.substring(1, u.length() - 1))); return sb.toString(); }
  • μ£Όμ–΄μ§„ "κ· ν˜•μž‘νžŒ κ΄„ν˜Έ λ¬Έμžμ—΄"을 "μ˜¬λ°”λ₯Έ κ΄„ν˜Έ λ¬Έμžμ—΄"둜 λ³€ν™˜ν•˜λŠ” ν•¨μˆ˜

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Solution { public String solution(String p) { // 이미 μ˜¬λ°”λ₯Έ 경우 λ°˜ν™˜ if (isProper(p)) return p; // μ˜¬λ°”λ₯΄μ§€ μ•Šμ€ 경우 return recursive(p); } private String recursive(String p) { // 빈 λ¬Έμžμ—΄μΈ 경우 λ°˜ν™˜ if (Objects.equals(p, "")) return p; // u와 v둜 뢄리 String[] uv = splitString(p); String u = uv[0]; String v = uv[1]; // uκ°€ μ˜¬λ°”λ₯΄λ‹€λ©΄, v에 λŒ€ν•΄ recurvie()ν•œ κ²°κ³Όλ₯Ό λΆ™μ—¬ λ°˜ν™˜ if (isProper(u)) return u + recursive(v); // uκ°€ μ˜¬λ°”λ₯΄μ§€ μ•Šμ€ 경우 StringBuilder sb = new StringBuilder("("); sb.append(recursive(v)).append(")").append(reverseBracket(u.substring(1, u.length() - 1))); return sb.toString(); } // μ˜¬λ°”λ₯Έ κ΄„ν˜Έ λ¬Έμžμ—΄μΈμ§€ ν™•μΈν•˜λŠ” ν•¨μˆ˜, Stack μ‚¬μš© private boolean isProper(String p) { Stack<Character> stack = new Stack<>(); int idx = 0; while (idx < p.length()) { char ch = p.charAt(idx); if (ch == '(') stack.push(ch); else if (stack.size() > 0) stack.pop(); idx++; } return stack.isEmpty(); } // λΆ„λ¦¬ν•˜λŠ” ν•¨μˆ˜, (의 κ°œμˆ˜μ™€ )의 κ°œμˆ˜κ°€ 같은 κ²½μš°κΉŒμ§€κ°€ u, λ‚˜λ¨Έμ§€λŠ” v private String[] splitString(String p) { String u = ""; String v = ""; int lcount = 0; int rcount = 0; int idx = 0; while(idx < p.length()) { if (p.charAt(idx) == '(') lcount++; else rcount++; idx++; if (lcount == rcount) { u = p.substring(0, idx); v = p.substring(idx); break; } } return new String[] {u, v}; } // μ£Όμ–΄μ§„ λ¬Έμžμ—΄μ˜ μ²«λ²ˆμ§Έμ™€ λ§ˆμ§€λ§‰ 문자λ₯Ό μ œκ±°ν•˜κ³ , λ‚˜λ¨Έμ§€ 문자λ₯Ό λ’€μ§‘λŠ” ν•¨μˆ˜ private String reverseBracket(String str) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < str.length(); i++) sb.append(str.charAt(i) == '(' ? ")" : "("); return sb.toString(); } }

✏️ Review

  • ν•˜λΌλŠ” λŒ€λ‘œλ§Œ κ΅¬ν˜„ν•˜λ©΄ μ‰½κ²Œ ν’€λ¦¬λŠ” 문제!
  • μ–΄λ–€ ν•¨μˆ˜λ₯Ό ν•„μš”λ‘œ ν•˜λŠ”μ§€ λ‚˜λˆ„μ–΄ μƒκ°ν•˜κ³  κ΅¬ν˜„ν•΄λ³΄λŠ” μ—°μŠ΅ν•˜κΈ°μ— 쒋은 λ¬Έμ œμ˜€λ‹€.
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€